#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
using namespace std;

class Solution{
    public:
    //My answer
    int ans1(vector<int>& num, int val){
        vector<int> index, new_num;
        for(int i = 0; i != num.size(); i++){
            if(num[i] == val){
                index.push_back(i);
            }
            else{
                new_num.push_back(num[i]);
            }
        }
        for(int i = 0; i != new_num.size(); i++){
            num[i] = new_num[i];
        }
        return new_num.size();
    }
    //一个不错的答案
    int ans2(vector<int>& num, int val){
        vector<int> index, new_num;
        for(int i = 0; i != num.size(); i++){
            if(num[i] == val){
                continue;
            }
            else{
                new_num.push_back(num[i]);
            }
        }
        for(int i = 0; i != new_num.size(); i++){
            num[i] = new_num[i];
        }
        return new_num.size();
    }
    //双指针-->同向移动
    int ans3(vector<int>& num, int val){
        int length = num.size();
        int p = 0;
        for(int i = 0; i != length; i++){
            if(num[i] != val){
                num[p] = num[i];
                p++;
            }
        }
        return p;
    }
    //双指针优化-->相向移动，向数组中间
    int ans4(vector<int>& num, int val){
        int lf = 0, rg = num.size();
        while(lf < rg){
            if(num[lf] == val){
                num[lf] = num[rg-1];
                rg--;
            }
            else{
                lf++;
            }
        }
        return lf;
    }

    void show(vector<int>& num){
        cout << "[" << ends;
        for(int i = 0; i != num.size()-1; i++){
            cout << num[i] << "," << ends;
        }
        cout << num[num.size()-1] << "]" << endl;
    }

};

void test1(){
    vector<int> num = {3, 2, 2, 3};
    int val = 3;

    Solution s;
    //cout << s.ans1(num, val) << endl;
    //cout << s.ans2(num, val) << endl;
    //cout << s.ans3(num, val) << endl;
    cout << s.ans4(num, val) << endl;
    s.show(num);
}

void test2(){
    vector<int> num = {0, 1, 2, 2, 3, 0, 4, 2};
    int val = 2;
    
    Solution s;
    //cout << s.ans1(num, val) << endl;
    //cout << s.ans2(num, val) << endl;
    //cout << s.ans3(num, val) << endl;
    cout << s.ans4(num, val) << endl;
    s.show(num);
}
int main(void){
    test1();
    test2();

    return 0;
}